﻿/*
* File: construct subgroup function
* Author: Dongcheng Li
* Date: 20191014
* Purpose: construct subgroup of Zp*
* https://w.ketangpai.com/pages/homework/homework-detail.html
*/
#include <iostream>
#include<stack>
using namespace std;
/*
*Input: an integer p, an integer g
* Output : return the result of subgroup.
* Purpose : construct subgroup of Zp*
* Method : By using the Fermat’s Little Theorem.
*/
void construct_Subgroup(int p, int g) {
	int Elements_in_a_Subgroup;
	int counter = 0;
	int counter1 = 0;
	int first_Elements_in_a_Subgroup;
	int static_g = g;
	if (g < 1 && g >= p)//
	{
		cout << "输入不合法";
	}
	else {
		while (1)
		{
			Elements_in_a_Subgroup = g % p;
			counter1++;
			if (counter == 1 && Elements_in_a_Subgroup == 1)//The result returns to the origin
			{
				cout << Elements_in_a_Subgroup << " ";
				cout << "order:" << counter1;
				break;
			}
			if (counter == 0)
			{
				first_Elements_in_a_Subgroup = Elements_in_a_Subgroup;
				counter++;
			}
			g = static_g * g;//Constantly multiplying g
			cout << Elements_in_a_Subgroup << " ";
		}
	}
}
int main()
{
	int prime_P;
	int elements_G;
	cout << "P:" << endl;
	cin >> prime_P;
	cout << "g:" << endl;
	cin >> elements_G;
	construct_Subgroup(prime_P, elements_G);
}